package solution23;

public class Solution {
    // 分治法
    public ListNode mergeKLists(ListNode[] list) {
        if (list == null || list.length == 0) return null;
        int n = list.length;
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; i++) {
                list[i] = merge2Lists(list[i], list[i + k]);
            }
            n = k;
        }
        return list[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null ) return l2;
        if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = merge2Lists(l1.next, l2);
            return l1;
        } else {
            l2.next = merge2Lists(l1,l2.next);
            return l2;
        }
    }
}
